package now_coder.sort.ncs;

import java.util.*;

public class NC97 {

    static class Node{
        String key;
        int times;

        public Node(String key, int times){
            this.key = key;
            this.times = times;
        }
    }

    public String[][] topKstrings (String[] strings, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String string : strings) {
            if (map.containsKey(string)){
                map.put(string, map.get(string) + 1);
            } else {
                map.put(string, 1);
            }
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.times != o2.times)
                    return o2.times - o1.times;
                if (o1.key.equals(o2.key))
                    return 0;
                else {
                    return o1.key.compareTo(o2.key);
                }
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            Node node = new Node(entry.getKey(), entry.getValue());
            pq.add(node);
        }

        String[][] ans = new String[k][2];
        for (int i = 0; i < k; i++) {
            Node node = pq.poll();
            ans[i][0] = node.key;
            ans[i][1] = String.valueOf(map.get(node.key));
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new NC97().topKstrings(new String[]{"a", "b", "c", "b"}, 2)));
    }

}
